"When You Believe" nhận được đánh giá trái chiều từ David Browne, biên tập viên của tạp chí Entertainment Weekly.[11] Anh cho ca khúc một điểm C- và viết rằng "[ca khúc có] quá nhiều chất kết dính, những cây phong (một loại cây cảnh lấy nhựa với đặc trưng là lá sắc nhọn) sẽ gây ra sự ghen ghét, đố kỵ". Anh nhận xét khía cạnh tôn giáo của bài hát là "nhạt nhẽo" và cảm thấy rằng thông điệp truyền cảm hứng của nó mang tính ép buộc và quá chung chung.[11] Trong khi đánh giá album nhạc phim The Prince of Egypt, Stephen Thomas Erlewine của AllMusic đã gọi bản song ca là "bất ngờ -- và là một sự bất ngờ thiếu thú vị."[12] Paul Verna của tạp chí Billboard cho rằng "When You Believe" là một bản song ca "tràn đầy sức mạnh" và sau đó đánh giá cao bài hát khi đang nhận xét về album của Houston.[13]

"When You Believe" đã thắng Giải Oscar cho ca khúc trong phim hay nhất tại lễ trao giải Oscar năm 1999,[14] và Giải BFCA cho ca khúc trong phim hay nhất tại lễ trao giải Sự lựa chon của nhà phê bình lần thứ 4.[15] Ca khúc cũng nhận được đề cử ở hạng mục Ca khúc gốc hay nhất (trong một bộ phim điện ảnh) tại giải Quả cầu vàng năm 1999,[16] và ở hạng mục Soạn nhạc Hay nhất cho Sản phẩm Truyền thông Hình ảnh trong lễ trao giải Grammy 2000.[17]